class DinnerPlates
{
public:
    DinnerPlates(int capacity)
    {
        this->capacity = capacity;
    }

    void push(int val)
    {
        if (!notFull.empty())
        {
            int firstNotFull = *notFull.begin();
            if (stacks[firstNotFull].empty())
            {
                notEmpty.insert(firstNotFull);
            }
            stacks[firstNotFull].push(val);
            if (stacks[firstNotFull].size() == capacity)
            {
                notFull.erase(firstNotFull);
            }
        }
        else
        {
            stacks.push_back({});
            stacks.back().push(val);
            notEmpty.insert(stacks.size() - 1);
            if (capacity > 1)
            {
                notFull.insert(stacks.size() - 1);
            }
        }
    }

    int pop()
    {
        if (notEmpty.empty())
        {
            return -1;
        }
        int lastNotEmpty = *notEmpty.rbegin();
        if (stacks[lastNotEmpty].size() == capacity)
        {
            notFull.insert(lastNotEmpty);
        }
        int val = stacks[lastNotEmpty].top();
        stacks[lastNotEmpty].pop();
        if (stacks[lastNotEmpty].empty())
        {
            notEmpty.erase(lastNotEmpty);
        }
        return val;
    }

    int popAtStack(int index)
    {
        if (index >= stacks.size() || stacks[index].empty())
        {
            return -1;
        }
        if (stacks[index].size() == capacity)
        {
            notFull.insert(index);
        }
        if (stacks[index].size() == 1)
        {
            notEmpty.erase(index);
        }
        int val = stacks[index].top();
        stacks[index].pop();
        return val;
    }

private:
    set<int> notFull;
    set<int> notEmpty;
    vector<stack<int>> stacks;
    int capacity;
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAtStack(index);
 */